{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimize XOR"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #bit-manipulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #位运算"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimizeXor"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最小 XOR"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个正整数 <code>num1</code> 和 <code>num2</code> ，找出满足下述条件的整数 <code>x</code> ：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>x</code> 的置位数和 <code>num2</code> 相同，且</li>\n",
    "\t<li><code>x XOR num1</code> 的值 <strong>最小</strong></li>\n",
    "</ul>\n",
    "\n",
    "<p>注意 <code>XOR</code> 是按位异或运算。</p>\n",
    "\n",
    "<p>返回整数<em> </em><code>x</code> 。题目保证，对于生成的测试用例， <code>x</code> 是 <strong>唯一确定</strong> 的。</p>\n",
    "\n",
    "<p>整数的 <strong>置位数</strong> 是其二进制表示中 <code>1</code> 的数目。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>num1 = 3, num2 = 5\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>\n",
    "num1 和 num2 的二进制表示分别是 0011 和 0101 。\n",
    "整数 <strong>3</strong> 的置位数与 num2 相同，且 <code>3 XOR 3 = 0</code> 是最小的。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>num1 = 1, num2 = 12\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>\n",
    "num1 和 num2 的二进制表示分别是 0001 和 1100 。\n",
    "整数 <strong>3</strong> 的置位数与 num2 相同，且 <code>3 XOR 1 = 2</code> 是最小的。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= num1, num2 &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimize-xor](https://leetcode.cn/problems/minimize-xor/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimize-xor](https://leetcode.cn/problems/minimize-xor/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3\\n5', '1\\n12']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeXor(self, num1: int, num2: int) -> int:\n",
    "        c1 = num1.bit_count()\n",
    "        c2 = num2.bit_count()\n",
    "        while c2 < c1:\n",
    "            num1 &= num1 - 1  # 最低的 1 变成 0\n",
    "            c2 += 1\n",
    "        while c2 > c1:\n",
    "            num1 |= num1 + 1  # 最低的 0 变成 1\n",
    "            c2 -= 1\n",
    "        return num1\n",
    "\n",
    "# 作者：灵茶山艾府\n",
    "# 链接：https://leetcode.cn/problems/minimize-xor/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeXor(self, num1: int, num2: int) -> int:\n",
    "        cnt1 = num1.bit_count()\n",
    "        cnt2 = num2.bit_count()\n",
    "        if cnt2 <= cnt1:\n",
    "            for _ in range(cnt1 - cnt2):    # 需要在原数上去除的1的数量\n",
    "                num1 -= num1 & (-num1)  #去除最低位1\n",
    "        else:\n",
    "            target = cnt2 - cnt1 # 需要在原数上添加的1的数量\n",
    "            mask = 1\n",
    "            while target > 0:\n",
    "                if not num1 & mask: # 这一位是0，可以添加1\n",
    "                    num1 += mask\n",
    "                    target -= 1\n",
    "                mask <<= 1\n",
    "        return num1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeXor(self, num1: int, num2: int) -> int:\n",
    "        bin1 = list(bin(num1)[2:])\n",
    "        bin2 = list(bin(num2)[2:])\n",
    "        \n",
    "        bit1 = Counter(bin1)[\"1\"]\n",
    "        bit2 = Counter(bin2)[\"1\"]\n",
    "        diff = bit2 - bit1\n",
    "        \n",
    "        if diff == 0:\n",
    "            return num1\n",
    "        elif diff > 0:\n",
    "            n = len(bin1)\n",
    "            for i in range(n):\n",
    "                if bin1[n - 1 - i] == \"0\" and diff > 0:\n",
    "                    bin1[n - 1 - i] = \"1\"\n",
    "                    diff -= 1\n",
    "                    if diff == 0:\n",
    "                        break\n",
    "            if diff > 0:\n",
    "                bin1 = [\"1\" * diff] + bin1\n",
    "            return int(\"\".join(bin1), 2)\n",
    "        else:\n",
    "            n = len(bin1)\n",
    "            for i in range(n):\n",
    "                if bin1[n - 1 - i] == \"1\" and diff < 0:\n",
    "                    bin1[n - 1 - i] = \"0\"\n",
    "                    diff += 1\n",
    "                    if diff == 0:\n",
    "                        break\n",
    "            return int(\"\".join(bin1), 2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeXor(self, num1: int, num2: int) -> int:\n",
    "        c1 = num1.bit_count()\n",
    "        c2 = num2.bit_count()\n",
    "        while c2 < c1:\n",
    "            num1 &= num1 - 1  # 最低的 1 变成 0\n",
    "            c2 += 1\n",
    "        while c2 > c1:\n",
    "            num1 |= num1 + 1  # 最低的 0 变成 1\n",
    "            c2 -= 1\n",
    "        return num1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeXor(self, num1: int, num2: int) -> int:\n",
    "        a = bin(num2).count(\"1\")\n",
    "        b = bin(num1).count(\"1\")\n",
    "        t = num1\n",
    "        arr = [] \n",
    "        while t!=0:\n",
    "            c = t&(-t)\n",
    "            arr.append(c)\n",
    "            t -= c\n",
    "        print(arr)\n",
    "        if a<=b:\n",
    "            return sum(arr[-a:])\n",
    "        else:\n",
    "            arr = set(arr)\n",
    "            t = a-b\n",
    "            f = 0\n",
    "            ans = 0\n",
    "            while t!=0:\n",
    "                if 2**f not in arr:\n",
    "                    ans += 2**f\n",
    "                    t -= 1\n",
    "                f+=1\n",
    "        return ans + sum(arr)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeXor(self, num1: int, num2: int) -> int:\n",
    "        cnt1 = num1.bit_count()\n",
    "        cnt2 = num2.bit_count()\n",
    "        while cnt1 > cnt2:\n",
    "            num1 &= num1 - 1\n",
    "            cnt1 -= 1\n",
    "        while cnt1 < cnt2:\n",
    "            num1 |= num1 + 1\n",
    "            cnt1 += 1\n",
    "        return num1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeXor(self, num1: int, num2: int) -> int:\n",
    "        def calcOneCnt(x):\n",
    "            res = []\n",
    "            one_cnt = 0\n",
    "            while(x > 0):\n",
    "                res.append(x % 2)\n",
    "                one_cnt += x%2\n",
    "                x = x // 2\n",
    "            return res[::-1],one_cnt\n",
    "        num1_list, num1_one_cnt = calcOneCnt(num1)\n",
    "        num2_list, num2_one_cnt = calcOneCnt(num2)\n",
    "        result = []\n",
    "        book = set()\n",
    "        for i in range(len(num1_list)):\n",
    "            if(num1_list[i] == 1 and num2_one_cnt > 0):\n",
    "                num2_one_cnt -= 1\n",
    "                book.add(i)\n",
    "                result.append(1)\n",
    "            else:\n",
    "                result.append(0)\n",
    "        def calcNum(digit):\n",
    "            n = len(digit)\n",
    "            result = 0\n",
    "            for i in range(n):\n",
    "                result += digit[i] * 2**(n-1-i)\n",
    "            return result\n",
    "        if(num2_one_cnt == 0):\n",
    "            return calcNum(result)\n",
    "        else:\n",
    "            for i in range(len(result)-1,-1,-1):\n",
    "                if(i in book):\n",
    "                    continue\n",
    "                result[i] = 1\n",
    "                num2_one_cnt -= 1\n",
    "                if(num2_one_cnt == 0):\n",
    "                    break\n",
    "            if(num2_one_cnt > 0):\n",
    "                result = [1]*num2_one_cnt + result\n",
    "            return calcNum(result)\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeXor(self, num1: int, num2: int) -> int:\n",
    "        t = num2.bit_count()\n",
    "        ans = 0\n",
    "        for i in range(32, -1, -1):\n",
    "            if num1 & 1 << i and t:\n",
    "                ans |= 1 << i\n",
    "                t -= 1\n",
    "        for i in range(32):\n",
    "            if num1 & 1 << i == 0 and t:\n",
    "                ans |= 1 << i\n",
    "                t -= 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeXor(self, num1: int, num2: int) -> int:\n",
    "        k=bin(num2)[2:]\n",
    "        cnt=k.count(\"1\")\n",
    "        s=bin(num1)[2:]\n",
    "        ans=[\"0\"]*len(k)\n",
    "        for i in s:\n",
    "            if i==\"1\" and cnt>0:\n",
    "                ans.append(\"1\")\n",
    "                cnt-=1\n",
    "            else:\n",
    "                ans.append(\"0\")\n",
    "        j=len(ans)-1\n",
    "        while cnt>0:\n",
    "            if ans[j]==\"0\":\n",
    "                ans[j]=\"1\"\n",
    "                cnt-=1\n",
    "            j-=1\n",
    "        return int(\"\".join(ans),2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeXor(self, num1: int, num2: int) -> int:\n",
    "        c1 = num1.bit_count()\n",
    "        c2 = num2.bit_count()\n",
    "        while c2 < c1:\n",
    "            num1 &= num1 - 1  # 最低的 1 变成 0\n",
    "            c2 += 1\n",
    "        while c2 > c1:\n",
    "            num1 |= num1 + 1  # 最低的 0 变成 1\n",
    "            c2 -= 1\n",
    "        return num1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeXor(self, num1: int, num2: int) -> int:\n",
    "        cnt1 = num1.bit_count()\n",
    "        cnt2 = num2.bit_count()\n",
    "        if cnt2 <= cnt1:\n",
    "            for _ in range(cnt1 - cnt2):    # 需要在原数上去除的1的数量\n",
    "                num1 -= num1 & (-num1)  #去除最低位1\n",
    "        else:\n",
    "            target = cnt2 - cnt1 # 需要在原数上添加的1的数量\n",
    "            mask = 1\n",
    "            while target > 0:\n",
    "                if not num1 & mask: # 这一位是0，可以添加1\n",
    "                    num1 += mask\n",
    "                    target -= 1\n",
    "                mask <<= 1\n",
    "        return num1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeXor(self, num1: int, num2: int) -> int:\n",
    "        k=bin(num2)[2:]\n",
    "        cnt=k.count(\"1\")\n",
    "        s=bin(num1)[2:]\n",
    "        ans=[\"0\"]*len(k)\n",
    "        for i in s:\n",
    "            if i==\"1\" and cnt>0:\n",
    "                ans.append(\"1\")\n",
    "                cnt-=1\n",
    "            else:\n",
    "                ans.append(\"0\")\n",
    "        j=len(ans)-1\n",
    "        while cnt>0:\n",
    "            if ans[j]==\"0\":\n",
    "                ans[j]=\"1\"\n",
    "                cnt-=1\n",
    "            j-=1\n",
    "        return int(\"\".join(ans),2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeXor(self, num1: int, num2: int) -> int:\n",
    "        c1 = num1.bit_count()\n",
    "        c2 = num2.bit_count()\n",
    "        while c2 < c1:\n",
    "            num1 &= num1 - 1  # 最低的 1 变成 0\n",
    "            c2 += 1\n",
    "        while c2 > c1:\n",
    "            num1 |= num1 + 1  # 最低的 0 变成 1\n",
    "            c2 -= 1\n",
    "        return num1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeXor(self, num1: int, num2: int) -> int:\n",
    "        def ones(num: int) -> int:\n",
    "            x = 0\n",
    "            while num != 0:\n",
    "                num &= num - 1\n",
    "                x += 1\n",
    "            return x\n",
    "\n",
    "        bits1, bits2 = ones(num1), ones(num2)\n",
    "        \n",
    "        if bits1 == bits2:\n",
    "            return num1\n",
    "        elif bits1 < bits2:\n",
    "            a = (~num1) & 0xFFFFFFFF\n",
    "            for _ in range(bits2 - bits1):\n",
    "                a = a & (a-1)\n",
    "            # print(bin(num1), bin(a), bits2-bits1)\n",
    "            return num1 | ((~a) & 0xFFFFFFFF)\n",
    "        else:\n",
    "            a = num1\n",
    "            for _ in range(bits1 - bits2):\n",
    "                a = a & (a-1)\n",
    "            return a\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeXor(self, num1: int, num2: int) -> int:\n",
    "        n=32\n",
    "        c2=bin(num2).count(\"1\")\n",
    "        c1=bin(num1).count(\"1\")\n",
    "        print(c1,c2)\n",
    "        \n",
    "        b1=bin(num1)[2:]\n",
    "        b2=bin(num2)[2:]\n",
    "        print(b1,b2)\n",
    "        arr=\"\"\n",
    "        if c1==c2:\n",
    "            return num1\n",
    "        elif c1>c2:\n",
    "            for x in b1:\n",
    "                if x==\"1\" and c2>0:\n",
    "                    arr+=\"1\"\n",
    "                    c2-=1\n",
    "                else:\n",
    "                    arr+=\"0\"\n",
    "\n",
    "        elif c1<c2:\n",
    "            n=len(b1)\n",
    "            c=c2-c1\n",
    "        \n",
    "            for i in range(n-1,-1,-1):\n",
    "                if b1[i]==\"0\" and c>0:\n",
    "                    arr=\"1\"+arr\n",
    "                    c-=1\n",
    "                else:\n",
    "                    arr=b1[i]+arr\n",
    "            while c>0:\n",
    "                arr=\"1\"+arr\n",
    "                c=c-1\n",
    "        print(arr)\n",
    "        return int(arr,2)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeXor(self, num1: int, num2: int) -> int:\n",
    "        x = num2.bit_count()\n",
    "        cnt = [i for i in range(32) if num1 & (1<<i)]\n",
    "\n",
    "        dct= set(cnt)\n",
    "        if x == len(cnt):\n",
    "            return num1\n",
    "        if x > len(cnt):\n",
    "            res = 0\n",
    "            x -= len(cnt)\n",
    "            for y in range(35):\n",
    "                if not x:\n",
    "                    break\n",
    "                if y not in dct:\n",
    "                    res += 1<<y\n",
    "                    x -= 1\n",
    "            return res + num1\n",
    "        return sum(1<<i for i in cnt[-x:])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeXor(self, num1: int, num2: int) -> int:\n",
    "        c1 = num1.bit_count()\n",
    "        c2 = num2.bit_count()\n",
    "        while c2 < c1:\n",
    "            num1 &= num1 - 1  # 最低的 1 变成 0\n",
    "            c2 += 1\n",
    "        while c2 > c1:\n",
    "            num1 |= num1 + 1  # 最低的 0 变成 1\n",
    "            c2 -= 1\n",
    "        return num1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeXor(self, num1: int, num2: int) -> int:\n",
    "        diff = num1.bit_count()-num2.bit_count()\n",
    "        if not diff: return num1\n",
    "        if diff < 0:\n",
    "            bit = 1\n",
    "            while diff < 0:\n",
    "                if not num1 & bit:\n",
    "                    diff += 1\n",
    "                    num1 |= bit\n",
    "                bit <<= 1\n",
    "            return num1\n",
    "        while diff > 0:\n",
    "            bit = num1 & -num1 \n",
    "            num1 -= bit\n",
    "            diff -= 1\n",
    "        return num1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeXor(self, num1: int, num2: int) -> int:\n",
    "        c1 = num1.bit_count()\n",
    "        c2 = num2.bit_count()\n",
    "        while c2 < c1:\n",
    "            num1 &= num1 - 1  # 最低的 1 变成 0\n",
    "            c2 += 1\n",
    "        while c2 > c1:\n",
    "            num1 |= num1 + 1  # 最低的 0 变成 1\n",
    "            c2 -= 1\n",
    "        return num1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeXor(self, num1: int, num2: int) -> int:\n",
    "        def calcNum(digit):\n",
    "            n = len(digit)\n",
    "            result = 0\n",
    "            for i in range(n):\n",
    "                result += digit[i] * 2**(n-1-i)\n",
    "            return result\n",
    "\n",
    "        def calcOneCnt(x):\n",
    "            res = []\n",
    "            one_cnt = 0\n",
    "            while(x > 0):\n",
    "                res.append(x % 2)\n",
    "                one_cnt += x%2\n",
    "                x = x // 2\n",
    "            return res[::-1],one_cnt\n",
    "        num1_list, num1_one_cnt = calcOneCnt(num1)\n",
    "        num2_list, num2_one_cnt = calcOneCnt(num2)\n",
    "        result = []\n",
    "        book = set()\n",
    "        for i in range(len(num1_list)):\n",
    "            if(num1_list[i] == 1 and num2_one_cnt > 0):\n",
    "                num2_one_cnt -= 1\n",
    "                book.add(i)\n",
    "                result.append(1)\n",
    "            else:\n",
    "                result.append(0)\n",
    "\n",
    "        if(num2_one_cnt == 0):\n",
    "            return calcNum(result)\n",
    "        else:\n",
    "            for i in range(len(result)-1,-1,-1):\n",
    "                if(i in book):\n",
    "                    continue\n",
    "                result[i] = 1\n",
    "                num2_one_cnt -= 1\n",
    "                if(num2_one_cnt == 0):\n",
    "                    break\n",
    "            if(num2_one_cnt > 0):\n",
    "                result = [1]*num2_one_cnt + result\n",
    "            return calcNum(result)\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeXor(self, num1: int, num2: int) -> int:\n",
    "        cnt1 = str(bin(num2)).count('1')\n",
    "        x = 0\n",
    "        for i in range(31,-1, -1):\n",
    "            if (num1 >> i) & 1:\n",
    "                cnt1 -= 1\n",
    "                x |= 1 << i \n",
    "                if cnt1 == 0:\n",
    "                    break \n",
    "        #print(cnt1, bin(x) ) \n",
    "        if cnt1 == 0:\n",
    "            return x \n",
    "        else:\n",
    "            for i in range(32):\n",
    "                if (x >> i) & 1==0:\n",
    "                    x |= 1 << i \n",
    "                    cnt1 -= 1\n",
    "                    if cnt1 == 0:\n",
    "                        break \n",
    "            return x "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeXor(self, num1: int, num2: int) -> int:\n",
    "        c1 = num1.bit_count()\n",
    "        c2 = num2.bit_count()\n",
    "\n",
    "        while c2 < c1:\n",
    "            num1 &= num1 - 1\n",
    "            c2 += 1\n",
    "        \n",
    "        while c2 > c1:\n",
    "            num1 |= num1 + 1\n",
    "            c2 -= 1\n",
    "        return num1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeXor(self, num1: int, num2: int) -> int:\n",
    "        num1=bin(num1)[2:]\n",
    "        num2 = bin(num2)[2:]\n",
    "\n",
    "        num1='0'*32+num1\n",
    "        num1=num1[-32:]\n",
    "        num2='0'*32+num2\n",
    "        num2=num2[-32:]\n",
    "        count_1_in_num1 = sum([1 if i=='1' else 0 for i in num1])\n",
    "        count_1_in_num2 = sum([1 if i=='1' else 0 for i in num2])\n",
    "\n",
    "\n",
    "\n",
    "        _num = ''\n",
    "        for s in num1:\n",
    "            if s == '1' and count_1_in_num2>0:\n",
    "                _num+='1'\n",
    "                count_1_in_num2-=1\n",
    "            else:\n",
    "                _num+='0'\n",
    "        p_num =''\n",
    "        for i in range(len(_num)-1,-1,-1):\n",
    "            if _num[i]=='0' and count_1_in_num2>0:\n",
    "                p_num ='1'+p_num\n",
    "                count_1_in_num2-=1\n",
    "            else:\n",
    "                p_num=_num[i]+p_num\n",
    "        print(p_num)\n",
    "        return int(p_num,base=2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeXor(self, num1: int, num2: int) -> int:\n",
    "        c1 = num1.bit_count()\n",
    "        c2 = num2.bit_count()\n",
    "        while c2 < c1:\n",
    "            num1 &= num1 - 1  # 最低的 1 变成 0\n",
    "            c2 += 1\n",
    "        while c2 > c1:\n",
    "            num1 |= num1 + 1  # 最低的 0 变成 1\n",
    "            c2 -= 1\n",
    "        return num1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeXor(self, num1: int, num2: int) -> int:\n",
    "        def calcOneCnt(x):\n",
    "            res = []\n",
    "            one_cnt = 0\n",
    "            while(x > 0):\n",
    "                res.append(x % 2)\n",
    "                one_cnt += x%2\n",
    "                x = x // 2\n",
    "            return res[::-1],one_cnt\n",
    "        num1_list, num1_one_cnt = calcOneCnt(num1)\n",
    "        num2_list, num2_one_cnt = calcOneCnt(num2)\n",
    "        result = []\n",
    "        book = set()\n",
    "        for i in range(len(num1_list)):\n",
    "            if(num1_list[i] == 1 and num2_one_cnt > 0):\n",
    "                num2_one_cnt -= 1\n",
    "                book.add(i)\n",
    "                result.append(1)\n",
    "            else:\n",
    "                result.append(0)\n",
    "        def calcNum(digit):\n",
    "            n = len(digit)\n",
    "            result = 0\n",
    "            for i in range(n):\n",
    "                result += digit[i] * 2**(n-1-i)\n",
    "            return result\n",
    "        if(num2_one_cnt == 0):\n",
    "            return calcNum(result)\n",
    "        else:\n",
    "            for i in range(len(result)-1,-1,-1):\n",
    "                if(i in book):\n",
    "                    continue\n",
    "                result[i] = 1\n",
    "                num2_one_cnt -= 1\n",
    "                if(num2_one_cnt == 0):\n",
    "                    break\n",
    "            if(num2_one_cnt > 0):\n",
    "                result = [1]*num2_one_cnt + result\n",
    "            return calcNum(result)\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeXor(self, num1: int, num2: int) -> int:\n",
    "        # 如果两个数相同，异或为0，X从num1开始变，如果x置数大于num2，需要从低位将1变为0，否则将0变为1\n",
    "        n1, n2 = num1.bit_count(), num2.bit_count()\n",
    "        x = str(bin(num1))[2:]\n",
    "        print(f\"n1:{n1} {bin(num1)}, n2:{n2} {bin(num2)}, x:{x}\")\n",
    "        if n1 > n2: # 低位1变为0\n",
    "            target = n1-n2\n",
    "            cnt = 0\n",
    "            for i in range(len(x)-1, -1, -1):\n",
    "                if x[i] == '1':\n",
    "                    x = x[:i] + '0' + x[i+1:]\n",
    "                    cnt += 1\n",
    "                if cnt == target:\n",
    "                    break\n",
    "        elif n1 < n2: # 低位0变为1\n",
    "            target = n2 - n1 # 有target个0需要变为1\n",
    "            x = '0'*n2 + x\n",
    "            cnt = 0\n",
    "            for i in range(len(x)-1, -1, -1):\n",
    "                if x[i] == '0':\n",
    "                    x = x[:i] + '1' + x[i+1:]\n",
    "                    cnt += 1\n",
    "                if cnt == target:\n",
    "                    break\n",
    "        # print(f\"ans:{x}\")\n",
    "        return int(x, 2)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeXor(self, num1: int, num2: int) -> int:\n",
    "        bd1 = bin(num1)\n",
    "        bd1 = bd1[2:]\n",
    "        bd2 = bin(num2)\n",
    "        bd2 = bd2[2:]\n",
    "        l1 = len(bd1)\n",
    "        l2 = len(bd2)\n",
    "        if l1<l2:\n",
    "            for i in range(l2-l1):\n",
    "                bd1 = '0' + bd1\n",
    "        else:\n",
    "            for i in range(l1-l2):\n",
    "                bd2 = '0' + bd2\n",
    "        c2 = bd2.count('1')\n",
    "        c0 = bd2.count('0')\n",
    "        n = len(bd1)\n",
    "        l = []\n",
    "        for i in range(n):\n",
    "            if c0==0:\n",
    "                l.append(1)\n",
    "            else:\n",
    "                if c2==0:\n",
    "                    l.append(0)\n",
    "                else:\n",
    "                    if bd1[i]=='1':\n",
    "                        l.append(1)\n",
    "                        c2-=1\n",
    "                    else:\n",
    "                        l.append(0)\n",
    "                        c0 -= 1\n",
    "        ans = 0\n",
    "        c = 0\n",
    "        for i in range(len(l)-1,-1,-1):\n",
    "            ans+=l[i]*(2**c)\n",
    "            c+=1\n",
    "        return ans\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeXor(self, num1: int, num2: int) -> int:\n",
    "        x, y = num1.bit_count(), num2.bit_count()\n",
    "        while x < y:\n",
    "            num1 |= num1 + 1\n",
    "            y -= 1\n",
    "        while x > y:\n",
    "            num1 &= num1 - 1\n",
    "            y += 1\n",
    "        return num1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeXor(self, num1: int, num2: int) -> int:\n",
    "        ones = 0\n",
    "        while num2:\n",
    "            if num2%2:\n",
    "                ones += 1\n",
    "            num2 >>= 1\n",
    "        pos = []\n",
    "        i = 0\n",
    "        while num1:\n",
    "            if num1%2:\n",
    "                pos.append(1)\n",
    "            else:\n",
    "                pos.append(0)\n",
    "            num1 >>= 1\n",
    "        pos = pos[::-1]\n",
    "        res = []\n",
    "        \n",
    "        for i,j in enumerate(pos):\n",
    "            if len(pos)-i <= ones:\n",
    "                for _ in range(ones):\n",
    "                    res.append(1)\n",
    "                break\n",
    "            if j == 1:\n",
    "                if ones > 0:\n",
    "                    res.append(1)\n",
    "                    ones -= 1\n",
    "                else:\n",
    "                    res.append(0)\n",
    "            else:\n",
    "                res.append(0)\n",
    "        rr = 0\n",
    "        #print(res,pos)\n",
    "        for r in res:\n",
    "            rr <<= 1\n",
    "            rr += r\n",
    "                 \n",
    "        return rr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeXor(self, num1: int, num2: int) -> int:\n",
    "        c1 = num1.bit_count()\n",
    "        c2 = num2.bit_count()\n",
    "\n",
    "        while c2 < c1:\n",
    "            num1 &= num1 - 1  # 最低的 1 变成 0\n",
    "            c2 += 1\n",
    "            \n",
    "        while c2 > c1:\n",
    "            num1 |= num1 + 1  # 最低的 0 变成 1\n",
    "            c2 -= 1\n",
    "\n",
    "        return num1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minimizeXor(self, num1: int, num2: int) -> int:\r\n",
    "        #统计num2的二进制1的个数\r\n",
    "        cnt1, cnt2 = num1.bit_count(), num2.bit_count()\r\n",
    "        #1. num1的1个数和num2相同,直接返回num1\r\n",
    "        #2. num1的1个数比num2少1，num1从低位开始，第一个0变成1，1还是1，cnt++\r\n",
    "        #3. num1的1个数比num2多1, num1从高位开始，第一个1变成0，0还是0，cnt--\r\n",
    "        cnt = cnt1 - cnt2\r\n",
    "        if cnt == 0:\r\n",
    "            return num1\r\n",
    "        elif cnt < 0:\r\n",
    "            #从低位开始，第一个0变成1,1还是1，cnt++\r\n",
    "            while cnt < 0:\r\n",
    "                num1 |= (num1 + 1)\r\n",
    "                cnt += 1\r\n",
    "        else:\r\n",
    "            #从高位开始，第一个1变成0,0还是0，cnt--\r\n",
    "            while cnt > 0:\r\n",
    "                num1 &= (num1 - 1)\r\n",
    "                cnt -= 1\r\n",
    "        return num1\r\n",
    "        \r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeXor(self, num1: int, num2: int) -> int:\n",
    "        n1 = 0\n",
    "        while num2:\n",
    "            if num2 % 2:\n",
    "                n1 += 1\n",
    "            num2 //= 2\n",
    "        a = []\n",
    "        while num1:\n",
    "            a.append(num1 % 2)\n",
    "            num1 //= 2\n",
    "        n = len(a)\n",
    "        if n <= n1:\n",
    "            return 2 ** n1 - 1\n",
    "        n0 = n - n1\n",
    "        for i in reversed(range(n)):\n",
    "            if a[i] == 1:\n",
    "                n1 -= 1\n",
    "                if n1 < 0:\n",
    "                    for j in range(i+1):\n",
    "                        a[j] = 0\n",
    "                    break\n",
    "            else:\n",
    "                n0 -= 1\n",
    "                if n0 < 0:\n",
    "                    for j in range(i+1):\n",
    "                        a[j] = 1\n",
    "                    break\n",
    "        res = 0\n",
    "        p = 1\n",
    "        for i in range(n):\n",
    "            if a[i] == 1:\n",
    "                res += p\n",
    "            p *= 2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeXor(self, num1: int, num2: int) -> int:\n",
    "        def bit_count(num: int) -> int:\n",
    "            cnt = 0\n",
    "            while num > 0:\n",
    "                if (num % 2 == 1):\n",
    "                    cnt += 1\n",
    "                num = num // 2\n",
    "            return cnt\n",
    "        \n",
    "        cnt1 = bit_count(num1)\n",
    "        cnt2 = bit_count(num2)\n",
    "\n",
    "        if (cnt1 == cnt2):\n",
    "            return num1\n",
    "        elif (cnt1 < cnt2):\n",
    "            delta = cnt2 - cnt1\n",
    "            ans, i = 0, 1\n",
    "            num2 = num1\n",
    "            while delta > 0:\n",
    "                if (num1 % 2 == 0):\n",
    "                    ans += i\n",
    "                    delta -=1\n",
    "                num1 = num1 // 2\n",
    "                i *= 2\n",
    "            return num2 + ans\n",
    "        else:\n",
    "            delta = cnt1 - cnt2\n",
    "            ans, i = 0, 1\n",
    "            num2 = num1\n",
    "            while delta > 0:\n",
    "                if (num1 % 2 == 1):\n",
    "                    ans += i\n",
    "                    delta -= 1\n",
    "                num1 = num1 // 2\n",
    "                i *= 2\n",
    "            return num2 - ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeXor(self, num1: int, num2: int) -> int:\n",
    "        a,b=num1.bit_count(),num2.bit_count()\n",
    "        print(str(bin(num1)),str(bin(num2)))\n",
    "        if b==a:\n",
    "            return num1\n",
    "        if b<a:\n",
    "            ret=0\n",
    "            k=b\n",
    "            #i=0\n",
    "            for i in range(len(str(bin(num1))),-1,-1):\n",
    "                if num1>>i&1:\n",
    "                    #print(i)\n",
    "                    ret+=pow(2,i)\n",
    "                    k-=1\n",
    "                    if k==0:\n",
    "                        break\n",
    "            #print(ret)\n",
    "            return ret\n",
    "        else:\n",
    "            ret=0\n",
    "            k=b-a\n",
    "            i=0\n",
    "            j=a.bit_length()\n",
    "            while k>0:\n",
    "                if num1>>i&1:\n",
    "                    i+=1\n",
    "                else:\n",
    "                    ret+=pow(2,i)\n",
    "                    k-=1\n",
    "                    i+=1\n",
    "            return num1^ret"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
